In some fields, it is useful to model real or computer-generated objects in three dimensions. Modeling such objects proves useful in a variety of applications. For example, modeling the subsurface structure of a portion of the earth's crust is useful for finding oil deposits, locating fault lines, and in other geological applications. Similarly, modeling human body parts is useful for medical training exercises, diagnoses, performing remote surgery, or for other medical applications. Modeling computer-generated objects is useful in creating computer games, designing flight simulations, and other applications. Other applications for 3D modeling of real and computer-generated objects exist.
Some 3D models represent an object as a 3D matrix of volume data points. Such a matrix, known as a data volume, includes a plurality of data points, known as volume data points. Each volume data point may be referred to as a volume pixel, also known as a voxel. A voxel is the smallest distinguishable box-shaped part of a 3D image. A voxel is similar to a pixel, but represents a 3D volume rather than a two-dimensional (2D) area. Each voxel represents a discrete sampling of a 3D portion of the object being modeled.
Once a data volume has been created, its contents can be displayed to users. A user may specify a 3D surface contained within the volume, and a display system displays the voxels on this surface on a screen or other display medium. This enables a user to view voxels that are contained in the interior of the data volume.
One system for displaying the voxels on an arbitrary 3D surface is known as 3D texture mapping. This technique is implemented in the raster processing unit of a computer graphics hardware accelerator. This technique uses a specific specialized memory, known as texture cache or texture memory, that is set aside on the integrated circuit.
Such a technique has certain inherent properties that render it inefficient for particular situations. For example, for data volumes that are large compared to the size of the available texture cache, the data volume must be broken up into blocks and each block must be swapped into the texture cache. This is inefficient because of the relatively large overhead required in determining the size of each block and reading it into the texture cache.
Furthermore, even though only the voxels that lie on the 3D surface may be needed by the raster processing unit in such a technique, every voxel in the data volume is read into and stored in the texture cache. Thus, memory in the texture cache is not used efficiently because a relatively large amount of unneeded data may be stored in the texture cache. This problem is exacerbated when the 3D surface is small compared to the data volume.
In addition, because a relatively large amount of texture cache is used in this operation, the amount of texture cache available to other graphics operations is limited. This limits the performance of the rendering of the object and limits the performance of other graphics operations.
Other techniques well-known in the art include subdividing a polygonal surface into multiple polygons and creating a texture tile for each polygon wherein each texture tile is used to form one or more texture atlases. A texture tile is a set of refined triangles and its bounding volume, which contains 3D texture data. A texture atlas is a group of texture tiles, which are usually arranged for the texture atlas to contain the maximum number of texture tiles. Such techniques, however, may still leave empty or unused space in each texture atlas that requires memory in the texture cache to store.